import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=56 lang=java
 *
 * [56] 合并区间
 */

// @lc code=start
class Solution {
    public int[][] merge(int[][] intervals) {
        
        Arrays.parallelSort(intervals, Comparator.comparingInt(x->x[0]));
        Deque<int[]> deque = new LinkedList<>();

        for (int i = 0; i < intervals.length; i++) {
            if (deque.isEmpty() || deque.getLast()[1] < intervals[i][0]) {
                deque.add(intervals[i]);
            } else {
                deque.getLast()[1] = Math.max(deque.getLast()[1], intervals[i][1]);
            }
        }       
        
        int[][] res = new int[deque.size()][2];

        int index = 0;
        while (!deque.isEmpty()) {
            res[index++] = deque.removeFirst();
        }

        return res;
    }
}
// @lc code=end

